package ACWing.Dynamicprogramming;
//895. 最长上升子序列
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/13 9:47
 */
public class TheLongestSubsequence {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n+1];
        for (int i = 1; i < n+1; i++) {
            arr[i]=sc.nextInt();
        }
//        int dp[]=new int[n+1];//朴素版本
//        for (int i = 1; i < n+1; i++) {
//            dp[i]=1;//默认自己是一给子序列单位为1
//            for (int j = 1; j <=i-1 ; j++) {
//                if(arr[i]>arr[j]){//严格递增不能相等
//                    dp[i]=Math.max(dp[j]+1,dp[i]);//状态转移方程
//                }
//
//            }
//        }
//        int max=0;
//        for (int i = 1; i <n+1 ; i++) {
//            max=Math.max(max,dp[i]);
//        }
//        System.out.println(max);
        //优雅解法从保存的dp中查找合适的插入点
        int[]dp=new int[n+1];//表示当前下标长度的最后一位的最小数
        int len=0;//保存最长距离
        for (int i = 1; i < n+1; i++) {//遍历每一个数查看自己的距离
            int l=0,r=len;
            while (l<r){//二分查找小于A【i】的最大数即插入点
                int mid=l+r+1>>1;
                if(dp[mid]<arr[i]) {
                    l = mid;
                }else r=mid-1;
            }
//            System.out.println(dp[r]+"  "+arr[i]);
            len=Math.max(len,r+1);
            dp[r+1]=arr[i];
//            System.out.println(len+" " +dp[r+1]);

        }
        System.out.println(len);
    }
}
